package com.hotcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: huangzhigao
 * @Date: 2023/2/26 15:45
 */
class LRUCache {

    class DoubleLinkedNode {
        private int key;
        private int value;
        private DoubleLinkedNode pre;
        private DoubleLinkedNode next;

        public DoubleLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public DoubleLinkedNode() {

        }
    }


    private Map<Integer, DoubleLinkedNode> cacheMap = new HashMap<>();
    private int capacity;
    private DoubleLinkedNode head;
    private DoubleLinkedNode tail;

    private int size;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DoubleLinkedNode();
        tail = new DoubleLinkedNode();
        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DoubleLinkedNode doubleLinkedNode = cacheMap.get(key);
        if (doubleLinkedNode == null) {
            return -1;
        }
        moveToHead(doubleLinkedNode);
        return doubleLinkedNode.value;
    }

    public void put(int key, int value) {
        DoubleLinkedNode doubleLinkedNode = cacheMap.get(key);

        if (doubleLinkedNode == null) {
            DoubleLinkedNode newNode = new DoubleLinkedNode(key, value);
            cacheMap.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                DoubleLinkedNode moveNode = removeTail();
                cacheMap.remove(moveNode.key);
                --size;
            }
        } else {
            doubleLinkedNode.value = value;
            moveToHead(doubleLinkedNode);
        }
    }


    public void addToHead(DoubleLinkedNode node) {
        node.pre = head;
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
    }

    public void moveToHead(DoubleLinkedNode node) {
        moveNode(node);
        addToHead(node);
    }

    public void moveNode(DoubleLinkedNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private DoubleLinkedNode removeTail() {
        DoubleLinkedNode res = tail.pre;
        moveNode(res);
        return res;
    }



}
